Mining Attribute-structure Correlated Patterns in Large Attributed Graphs

摘要

In this work, we study the correlation between attribute sets and theoccurrence of dense subgraphs in large attributed graphs, a task we callstructural correlation pattern mining. A structural correlation pattern is adense subgraph induced by a particular attribute set. Existing methods are notable to extract relevant knowledge regarding how vertex attributes interactwith dense subgraphs. Structural correlation pattern mining combines aspects offrequent itemset and quasi-clique mining problems. We propose statisticalsignificance measures that compare the structural correlation of attribute setsagainst their expected values using null models. Moreover, we evaluate theinterestingness of structural correlation patterns in terms of size anddensity. An efficient algorithm that combines search and pruning strategies inthe identification of the most relevant structural correlation patterns ispresented. We apply our method for the analysis of three real-world attributedgraphs: a collaboration, a music, and a citation network, verifying that itprovides valuable knowledge in a feasible time.